package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
最长递增子序列的长度
输入 4 2 3 1 5
输出 3 （因为 2 3 5组成了最长递增子序列）
in
5
4 2 3 1 5

out
3
 */
public class j最长递增子序列LISby暴力 {
	public static void main(String[] args) {
		j最长递增子序列LISby暴力 test = new j最长递增子序列LISby暴力();
		test.useForce();
	}
	
	/**
	 * 前置方法
	 */
	public void useForce() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = scanner.nextInt();
		}
		int res = force(N, arr);
		System.out.println(res);
	}
	
	/**
	 * O(N^2)
	 * @param N
	 * @param arr
	 * @return
	 */
	public int force(int N, int[] arr) {
		int maxLength = -1;
		for (int current = 0; current < N; current++) {//尝试把每个元素作为“最长子序列”的首元素
			int nextMax = current;//定义当前“最长子序列”最大的元素的索引
			int count = 1;//定义当前“最长子序列”的长度；从1开始是因为"最长子序列"最短也还有1个元素
			for (int i = current + 1; i < N; i++) {//对剩下的元素进行遍历，判断有没有资格进入当前“最长子序列”
				if (arr[nextMax] < arr[i]) {//有资格
					count++;
					nextMax = i;//更新当前“最长子序列”最大的元素的索引
				}
			}
			maxLength = Math.max(maxLength, count);//当前“最长子序列”是否 > 历史“最长子序列”
		}
		return maxLength;
	}
}
